﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    public class T_0020_ReverseList
    {
        // 反转链表

        // 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

        // 提示：
        //   链表中节点的数目范围是[0, 5000]
        //   -5000 <= Node.val <= 5000

        //   进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

        public void Test()
        {
            var list = new ListNode(1)
            {
                next = new ListNode(3)
                {
                    next = new ListNode(5)
                    {
                        next = new ListNode(9)
                    }
                }
            };
            var result = ReverseList(list);
            while (result != null)
            {
                Console.WriteLine(result.val);
                result = result.next;
            }
            Console.Read();
        }


        // 双链表
        public ListNode ReverseList(ListNode head)
        {
            if (head == null)
                return null;
            var result = new ListNode(head.val);
            while (head.next != null)
            {
                head = head.next;
                result = new ListNode(head.val, result);
            }
            return result;
        }

        // 双链表优化
        public ListNode reverseList(ListNode head)
        {
            //新链表
            ListNode newHead = null;
            while (head != null)
            {
                //先保存访问的节点的下一个节点，保存起来
                //留着下一步访问的
                ListNode temp = head.next;
                //每次访问的原链表节点都会成为新链表的头结点，
                //其实就是把新链表挂到访问的原链表节点的
                //后面就行了
                head.next = newHead;
                //更新新链表
                newHead = head;
                //重新赋值，继续访问
                head = temp;
            }
            //返回新链表
            return newHead;
        }

        // 栈
        public ListNode ReverseList1(ListNode head)
        {
            Stack<ListNode> stack = new Stack<ListNode>();
            //把链表节点全部摘掉放到栈中
            while (head != null)
            {
                stack.Push(head);
                head = head.next;
            }
            if (stack.Count == 0)
                return null;
            ListNode node = stack.Pop();
            ListNode dummy = node;
            //栈中的结点全部出栈，然后重新连成一个新的链表
            while (stack.Count != 0)
            {
                ListNode tempNode = stack.Pop();
                node.next = tempNode;
                node = node.next;
            }
            //最后一个结点就是反转前的头结点，一定要让他的next
            //等于空，否则会构成环
            node.next = null;
            return dummy;
        }

        // 递归
        public ListNode ReverseList2(ListNode head)
        {
            if (head == null || head.next == null)
                return head;
            ListNode reverse = ReverseList2(head.next);
            head.next.next = head;
            head.next = null;
            return reverse;
        }

        // 尾递归
        public ListNode ReverseList4(ListNode head)
        {
            return ReverseListInt(head, null);
        }

        private ListNode ReverseListInt(ListNode head, ListNode newHead)
        {
            if (head == null)
                return newHead;
            ListNode next = head.next;
            head.next = newHead;
            return ReverseListInt(next, head);
        }

    }
}
